import java.util.Stack;

public class Solution {
    public static void main(String[] args) {
        String s = "()[]{}";
        System.out.println(isValid(s));
    }
    //括号匹配
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        int i;
        for( i = 0; i < s.length(); i++) {
            char a = s.charAt(i);
            if(a == '(' || a == '[' || a == '{') {
                stack.push(a);
            }
            else{
                if(stack.isEmpty()) {
                    //栈空，队列不为空
                    return false;
                }
                if(a == ')' && stack.peek() == '('
                        || a == ']' && stack.peek() == '['
                        || a == '}' && stack.peek() == '{') {
                    stack.pop();
                }else{
                    //括号不匹配
                    return false;
                }
            }
        }
        //栈不为空
        if(stack.isEmpty()) {
            return true;
        }
        return false;
    }
}
